// 用一个变量代替两个变量
// 时间复杂度：O(mn)
// 空间复杂度：O(1)
void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = matrixColSize[0];

    // 先计算第一列是否包含 0
    bool flagCol1 = 0;

    // 使用 matrix 的第一行和第一列来记录每行每列是否包含 0
    for (int row = 0; row < m; row++) {
        // 计算第一列是否包含 0
        if (matrix[row][0] == 0) flagCol1 = true;
        for (int col = 1; col < n; col++) {
            if (matrix[row][col] == 0) {
                matrix[0][col] = 0;
                matrix[row][0] = 0;
            }
        }
    }
    // bug 修复：row--
    for (int row = m - 1; row >= 0; row--) {
        for (int col = 1; col < n; col++) {
            if (matrix[0][col] == 0 || matrix[row][0] == 0) {
                matrix[row][col] = 0;
            }
        }
        if (flagCol1) {
            matrix[row][0] = 0;
        }
    }
}

// 用两个变量代替两个数组
// 时间复杂度：O(mn)
// 空间复杂度：O(1)
void setZeroes2(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = matrixColSize[0];

    // 先计算第一行第一列是否包含 0
    bool flagRow1 = false;
    for (int i = 0; i < n; i++) {
        if (matrix[0][i] == 0) flagRow1 = true;
    }

    bool flagCol1 = false;
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) flagCol1 = true;
    }

    // 使用 matrix 的第一行和第一列来记录每行每列是否包含 0
    for (int row = 1; row < m; row++) {
        for (int col = 1; col < n; col++) {
            if (matrix[row][col] == 0) {
                matrix[0][col] = 0;
                matrix[row][0] = 0;
            }
        }
    }

    for (int row = 1; row < m; row++) {
        for (int col = 1; col < n; col++) {
            if (matrix[0][col] == 0 || matrix[row][0] == 0) {
                matrix[row][col] = 0;
            }
        }
    }

    if (flagRow1) {
        for (int i = 0; i < n; i++) {
            matrix[0][i] = 0;
        }
    }
    if (flagCol1) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
}

// 用两个辅助数组实现
// 时间复杂度：O(mn)
// 空间复杂度：O(m + n)
void setZeroes1(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = matrixColSize[0];

    // 标记需要设置为 0 的行和列
    bool* rows = (bool*)malloc(sizeof(bool) * m);
    bool* cols = (bool*)malloc(sizeof(bool) * n);
    memset(rows, false, sizeof(bool) * m);
    memset(cols, false, sizeof(bool) * n);

    for (int row = 0; row < m; row++) {
        for (int col = 0; col < n; col++) {
            if (matrix[row][col] == 0) {
                rows[row] = true;
                cols[col] = true;
            }
        }
    }

    for (int row = 0; row < m; row++) {
        for (int col = 0; col < n; col++) {
            if (rows[row] || cols[col]) {
                matrix[row][col] = 0;
            }
        }
    }
    free(rows);
    free(cols);
}